/*************************************************************************
 *
 *  The Contents of this file are made available subject to the terms of
 *  either of the following licenses
 *
 *         - GNU Lesser General Public License Version 2.1
 *         - Sun Industry Standards Source License Version 1.1
 *
 *  Sun Microsystems Inc., October, 2000
 *
 *  GNU Lesser General Public License Version 2.1
 *  =============================================
 *  Copyright 2000 by Sun Microsystems, Inc.
 *  901 San Antonio Road, Palo Alto, CA 94303, USA
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License version 2.1, as published by the Free Software Foundation.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *  MA  02111-1307  USA
 *
 *
 *  Sun Industry Standards Source License Version 1.1
 *  =================================================
 *  The contents of this file are subject to the Sun Industry Standards
 *  Source License Version 1.1 (the "License"); You may not use this file
 *  except in compliance with the License. You may obtain a copy of the
 *  License at http://www.openoffice.org/license.html.
 *
 *  Software provided under this License is provided on an "AS IS" basis,
 *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
 *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
 *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
 *  See the License for the specific provisions governing your rights and
 *  obligations concerning the Software.
 *
 *  The Initial Developer of the Original Code is: IBM Corporation
 *
 *  Copyright: 2008 by IBM Corporation
 *
 *  All Rights Reserved.
 *
 *  Contributor(s): _______________________________________
 *
 *
 ************************************************************************/
#include <assert.h>
#include "explode.hxx"
#include <math.h>
	const static char Tree1String[][32] = {
		"101",
		"11",
	       "100", 
		"011", 
		"0101",
		"0100",
		"0011",
		"00101",
		"00100",
		"00011",
		"00010",
		"000011",
		"000010",
		"000001",
		"0000001",
		"0000000",
	};

	const static char Tree2String[][32] = {
		"11"    ,
		"1011"  ,
	       "1010"  ,
		"10011"  ,
		"10010"  ,
		"10001"  ,
		"10000"  ,
		"011111"  ,
		"011110"  ,
		"011101"  ,
		"011100"  ,
		"011011"  ,
		"011010"  ,
		"011001"  ,
		"011000"  ,
		"010111"  ,
		"010110" ,
		"010101" ,
		"010100" ,
		"010011" ,
		"010010" ,
		"010001" ,
		"0100001" ,
		"0100000" ,
		"0011111" ,
		"0011110" ,
		"0011101" ,
		"0011100" ,
		"0011011" ,
		"0011010" ,
		"0011001" ,
		"0011000" ,
		"0010111" ,
		"0010110" ,
		"0010101" ,
		"0010100" ,
		"0010011" ,
		"0010010" ,
		"0010001" ,
		"0010000" ,
		"0001111" ,
		"0001110" ,
		"0001101" ,
		"0001100" ,
		"0001011" ,
		"0001010" ,
		"0001001" ,
		"0001000" ,
		"00001111",
		"00001110",
		"00001101",
		"00001100",
		"00001011",
		"00001010",
		"00001001",
		"00001000",
		"00000111",
		"00000110",
		"00000101",
		"00000100",
		"00000011",
		"00000010",
		"00000001",
		"00000000",
	};

Decompression::Decompression(SvStream * pInStream, SvStream * pOutStream):
	m_pInStream(pInStream), m_pOutStream(pOutStream), m_pBuffer(m_Buffer), m_nOutputBufferPos(0),
		m_nBitsLeft(0), m_nBytesLeft(0), m_nCurrent4Byte(0)
{
	if (!m_pInStream || !m_pOutStream )
	{
		assert(sal_False);
	}
	ConstructTree1();
	ConstructTree2();
	fillArray();
}
/**
 * @descr	read specified bits from input stream
 * @argument iCount - number of bits to be read, less than 31
 * @argument nBits - bits read
 * @return 	0 - read OK, otherwise error
 */
sal_uInt32 Decompression::ReadBits(sal_uInt16 iCount, sal_uInt32 & nBits) 
{
	if ( (iCount == 0) || (iCount > 32 ) )
	{
		return -1;
	}
	
	sal_uInt32 val = 0;		/* bit accumulator */

	/* load at least need bits into val */
	val = m_nCurrent4Byte;
	while (m_nBitsLeft < iCount) 
	{
		if (m_nBytesLeft == 0) 
		{
			m_nBytesLeft = m_pInStream->Read(m_Buffer, CHUNK);
			m_pBuffer = m_Buffer;
			if (m_nBytesLeft == 0)  return -1; 
	        }
		val |= (sal_uInt32)(*m_pBuffer++) << m_nBitsLeft;		/* load eight bits */
		m_nBytesLeft --;
		m_nBitsLeft += 8;
	}

	/* drop need bits and update buffer, always zero to seven bits left */
	m_nCurrent4Byte = val >> iCount;
	m_nBitsLeft -= iCount;

	/* return need bits, zeroing the bits above that */
	nBits = val & ((1 << iCount) - 1);

	return 0;	
} 
/**
 * @descr	decompress input and write output
 * @return 	0 - read OK, otherwise error
 */
sal_Int32 Decompression::explode()
{
	/* The first 2 bytes are parameters */
	sal_uInt32 P1;
	if (0 != ReadBits(8, P1))/* 0 or 1 */
		return -1;
	
	/* I think this means 0=binary and 1=ascii file, but in RESOURCEs I saw always 0 */
	if (P1 >= 1) // changed per 's review comments
		return -1;
	
	sal_uInt32 P2;
	if (0 != ReadBits(8, P2))
		return -1;
	
	/* must be 4,5 or 6 and it is a parameter for the decompression algorithm */
	if (P2 < 4 || P2 > 6) 
		return -2;

	m_nOutputBufferPos = 0;
	/* Now, a bit stream follows, which is decoded as described below: */
	/*  The algorithm terminates as soon as it runs out of bits. */
	while(sal_True)
	{
		// read 1 bit (take bits from the lowest value (LSB) to the MSB i.e. bit 0, bit 1 etc ...)
		sal_uInt32 iBit;
		if (0 != ReadBits(1, iBit))
			break;
		if ( 0 == (iBit & 0x01) )
		{
			//if the bit is 0 read 8 bits and write it to the output as it is.
			sal_uInt32 symbol;
			if (0 != ReadBits(8, symbol))
				break;
			m_Output[m_nOutputBufferPos++] = (sal_uInt8)symbol;
			if (m_nOutputBufferPos == MAXWIN) 
			{
				m_pOutStream->Write(m_Output, m_nOutputBufferPos);
				m_nOutputBufferPos = 0;
			}
			continue;
		}
		// if the bit is 1 we have here a length/distance pair:
		// -decode a number with Hufmman Tree #1; variable bit length, result is 0x00 .. 0x0F -> L1
		sal_uInt32 L1 = Decode(m_Tree1);
		sal_uInt32 Length;
		if (L1 <= 7)
		{
			//if L1 <= 7:
			//           LENGTH = L1 + 2
			Length = L1 + 2;
		}
		else
		{
			// if L1 > 7
			//            read more (L1-7) bits -> L2
			//             LENGTH = L2 + M[L1-7] + 2
			sal_uInt32 L2;
			if (0 != ReadBits((sal_uInt16)(L1 - 7), L2))
				break;
			Length = L2 + 2 + m_iArrayOfM[L1 -7];
		}
		if (Length == 519)
		{
			// end of compressed data
			break;
		}
		
		// - decode another number with Hufmann Tree #2 giving result 0x00..0x3F -> D1
		sal_uInt32 D1 = Decode(m_Tree2);
		sal_uInt32 D2;
		if (Length == 2)
		{
			//       if LENGTH == 2
			//              D1 = D1 << 2
			//              read 2 bits -> D2
			D1 = D1 << 2;
			if (0 != ReadBits(2, D2))
				break;
		}
		else
		{
			//        else
			//               D1 = D1 << P2  // the parameter 2
			//               read P2 bits -> D2
			D1 = D1 << P2;
			if (0 != ReadBits(P2, D2))
				break;
		}
		// DISTANCE = (D1 | D2) + 1			
		sal_uInt32 distance = (D1 | D2) + 1;

	        // - now copy LENGTH bytes from (output_ptr-DISTANCE) to output_ptr		
	        // write current buffer to output
		m_pOutStream->Write(m_Output, m_nOutputBufferPos);
		m_nOutputBufferPos = 0;

		// remember current position
		sal_uInt32 nOutputPos = m_pOutStream->Tell();
		if (distance > nOutputPos)
			return -3; // format error

		m_pOutStream->Flush();
		// point back to copy position and read bytes
		m_pOutStream->SeekRel((long)-distance);
		sal_uInt8 sTemp[MAXWIN];
		sal_uInt32 nRead = distance > Length? Length:distance;
		m_pOutStream->Read(sTemp, nRead);
		if (nRead != Length)
		{
			// fill the buffer with read content repeatly until full
			for (sal_uInt32 i=nRead; i<Length; i++)
			{
				sTemp[i] = sTemp[i-nRead];
			}
		}

		// restore output stream position
		m_pOutStream->Seek(nOutputPos);
		
	       // write current buffer to output
		m_pOutStream->Write(sTemp, Length);
	}
	return 0;
}
/**
 * @descr	bits to string
 * @return 	
 */
void Decompression::ToString(sal_uInt32 nBits, sal_Char *pChar, sal_uInt32 nLen)
{
	sal_uInt32 nBit;
	for (sal_uInt32 i=nLen; i > 0; i--)
	{
		nBit = (nBits >> (i -1) ) & 0x01;
		pChar[nLen - i]  = nBit ? '1':'0';
	}
	pChar[nLen] = '\0';
	return;
}

/**
 * @descr	decode tree 1 for length
 * @return 	the decoded value
 */
sal_uInt32 Decompression::Decode(HuffmanTreeNode * pRoot)
{
	sal_uInt32 nRet;
	sal_uInt32 nRead, nReadAlready;
	
	if( 0 != ReadBits(1, nReadAlready))
		return 0; // something wrong

	for (sal_uInt16 i=2; i <= 8; i++)
	{
		if ( 0 != ReadBits(1, nRead))
			return 0; // something wrong
			
		nReadAlready  = (nReadAlready << 1) | (nRead & 0x01);

		sal_Char sCode[16];
		ToString(nReadAlready, sCode, i);
		nRet = pRoot->QueryValue(sCode);	
		if (nRet != 0xffffffff)
		{
			break;
		}
	}
	return nRet;
}
/**
 * @descr	construct tree 1 for length
 * @return 	
 */
void Decompression::ConstructTree1()
{	// Huffman Tree #1
	// The first huffman tree (the Section called Decompression algorithm HUFFMAN) contains the length values. It is described by the following table: 
	// value (hex)	code (binary)
	// 0	101
	// 1	11
	// 2	100
	// 3	011
	// 4	0101
	// 5	0100
	// 6	0011
	// 7	0010 1
	// 8	0010 0
	// 9	0001 1
	// a	0001 0
	// b	0000 11
	// c	0000 10
	// d	0000 01
	// e	0000 001
	// f	0000 000
	m_Tree1 = new HuffmanTreeNode();
	for (sal_uInt32 i=0; i< 16; i++)
	{
	    m_Tree1->InsertNode(i, Tree1String[i]);
	}
	/*
	m_Tree1->InsertNode(0,   "101");
	m_Tree1->InsertNode(1,   "11");
	m_Tree1->InsertNode(2,   "100");
	m_Tree1->InsertNode(3,   "011");
	m_Tree1->InsertNode(4,   "0101");
	m_Tree1->InsertNode(5,   "0100");
	m_Tree1->InsertNode(6,   "0011");
	m_Tree1->InsertNode(7,   "00101");
	m_Tree1->InsertNode(8,   "00100");
	m_Tree1->InsertNode(9,   "00011");
	m_Tree1->InsertNode(10, "00010");
	m_Tree1->InsertNode(11, "000011");
	m_Tree1->InsertNode(12, "000010");
	m_Tree1->InsertNode(13, "000001");
	m_Tree1->InsertNode(14, "0000001");
	m_Tree1->InsertNode(15, "0000000");
	*/
}
/**
 * @descr	construct tree 2 for distance
 * @return 	
 */
void Decompression::ConstructTree2()
{

	m_Tree2 = new HuffmanTreeNode();
	for (sal_uInt32 i=0; i< 64; i++)
	{
	    m_Tree2->InsertNode(i, Tree2String[i]);
	}
#if 0
	m_Tree2 = new HuffmanTreeNode();
    //Huffman Tree #2
    //The second huffman code tree contains the distance values. It can be built from the following table:
    //value (hex) code (binary)
    //00  11
    //01  1011
    //02  1010
    //03  1001 1
    //04  1001 0
    //05  1000 1
    //06  1000 0
    //07  0111 11
    //08  0111 10
    //09  0111 01
    //0a  0111 00
    //0b  0110 11
    //0c  0110 10
    //0d  0110 01
    //0e  0110 00
    //0f  0101 11
	m_Tree2->InsertNode(0x0,   "11");
	m_Tree2->InsertNode(0x1,   "1011");
	m_Tree2->InsertNode(0x2,   "1010");
	m_Tree2->InsertNode(0x3,   "10011");
	m_Tree2->InsertNode(0x4,   "10010");
	m_Tree2->InsertNode(0x5,   "10001");
	m_Tree2->InsertNode(0x6,   "10000");
	m_Tree2->InsertNode(0x7,   "011111");
	m_Tree2->InsertNode(0x8,   "011110");
	m_Tree2->InsertNode(0x9,   "011101");
	m_Tree2->InsertNode(0x0a,  "011100");
	m_Tree2->InsertNode(0x0b,  "011011");
	m_Tree2->InsertNode(0x0c,  "011010");
	m_Tree2->InsertNode(0x0d,  "011001");
	m_Tree2->InsertNode(0x0e,  "011000");
	m_Tree2->InsertNode(0x0f,  "010111");
	//10  0101 10
	//11  0101 01
	//12  0101 00
	//13  0100 11
	//14  0100 10
	//15  0100 01
	//16  0100 001
	//17  0100 000
	//18  0011 111
	//19  0011 110
	// 1a  0011 101
	// 1b  0011 100
	// 1c  0011 011
	// 1d  0011 010
	// 1e  0011 001
	// 1f  0011 000
	m_Tree2->InsertNode(0x10,   "010110");
	m_Tree2->InsertNode(0x11,   "010101");
	m_Tree2->InsertNode(0x12,   "010100");
	m_Tree2->InsertNode(0x13,   "010011");
	m_Tree2->InsertNode(0x14,   "010010");
	m_Tree2->InsertNode(0x15,   "010001");
	m_Tree2->InsertNode(0x16,   "0100001");
	m_Tree2->InsertNode(0x17,   "0100000");
	m_Tree2->InsertNode(0x18,   "0011111");
	m_Tree2->InsertNode(0x19,   "0011110");
	m_Tree2->InsertNode(0x1a,   "0011101");
	m_Tree2->InsertNode(0x1b,   "0011100");
	m_Tree2->InsertNode(0x1c,   "0011011");
	m_Tree2->InsertNode(0x1d,   "0011010");
	m_Tree2->InsertNode(0x1e,   "0011001");
	m_Tree2->InsertNode(0x1f,   "0011000");
    //20  0010 111
    //21  0010 110
    //22  0010 101
    //23  0010 100
    //24  0010 011
    //25  0010 010
    //26  0010 001
    //27  0010 000
    //28  0001 111
    //29  0001 110
    // 2a  0001 101
    // 2b  0001 100
    // 2c  0001 011
    // 2d  0001 010
    // 2e  0001 001
    // 2f  0001 000
	m_Tree2->InsertNode(0x20,   "0010111");
	m_Tree2->InsertNode(0x21,   "0010110");
	m_Tree2->InsertNode(0x22,   "0010101");
	m_Tree2->InsertNode(0x23,   "0010100");
	m_Tree2->InsertNode(0x24,   "0010011");
	m_Tree2->InsertNode(0x25,   "0010010");
	m_Tree2->InsertNode(0x26,   "0010001");
	m_Tree2->InsertNode(0x27,   "0010000");
	m_Tree2->InsertNode(0x28,   "0001111");
	m_Tree2->InsertNode(0x29,   "0001110");
	m_Tree2->InsertNode(0x2a,   "0001101");
	m_Tree2->InsertNode(0x2b,   "0001100");
	m_Tree2->InsertNode(0x2c,   "0001011");
	m_Tree2->InsertNode(0x2d,   "0001010");
	m_Tree2->InsertNode(0x2e,   "0001001");
	m_Tree2->InsertNode(0x2f,   "0001000");
    //30  0000 1111
    //31  0000 1110
    //32  0000 1101
    //33  0000 1100
    //34  0000 1011
    //35  0000 1010
    //36  0000 1001
    //37  0000 1000
    //38  0000 0111
    //39  0000 0110
    // 3a  0000 0101
    // 3b  0000 0100
    // 3c  0000 0011
    // 3d  0000 0010
    // 3e  0000 0001
    // 3f  0000 0000
	m_Tree2->InsertNode(0x30,   "00001111");
	m_Tree2->InsertNode(0x31,   "00001110");
	m_Tree2->InsertNode(0x32,   "00001101");
	m_Tree2->InsertNode(0x33,   "00001100");
	m_Tree2->InsertNode(0x34,   "00001011");
	m_Tree2->InsertNode(0x35,   "00001010");
	m_Tree2->InsertNode(0x36,   "00001001");
	m_Tree2->InsertNode(0x37,   "00001000");
	m_Tree2->InsertNode(0x38,   "00000111");
	m_Tree2->InsertNode(0x39,   "00000110");
	m_Tree2->InsertNode(0x3a,   "00000101");
	m_Tree2->InsertNode(0x3b,   "00000100");
	m_Tree2->InsertNode(0x3c,   "00000011");
	m_Tree2->InsertNode(0x3d,   "00000010");
	m_Tree2->InsertNode(0x3e,   "00000001");
	m_Tree2->InsertNode(0x3f,   "00000000");
#endif	
    //where bits should be read from the left to the right.
}
/**
 * @descr	
 * @return 	
 */
void Decompression::fillArray()
{
	m_iArrayOfM[0] = 7;
	for (sal_uInt32 i=1; i < 16; i++)
	{
		m_iArrayOfM[i]  = m_iArrayOfM[i - 1]+ (sal_uInt32)pow(2, i-1);//2
	}
}

HuffmanTreeNode::HuffmanTreeNode(sal_uInt32 nValue , HuffmanTreeNode * pLeft , HuffmanTreeNode * pRight ) 
{
	value = nValue;
	left = pLeft; 
	right = pRight;
}
HuffmanTreeNode::~HuffmanTreeNode() 
{
	if (left)
	{
		delete left;
		left = NULL;
	}
	if (right)
	{
		delete right;
		right = NULL;
	}		
}

HuffmanTreeNode * HuffmanTreeNode::InsertNode(sal_uInt32 nValue, const sal_Char * pInCode)
{
	HuffmanTreeNode *pNew = new HuffmanTreeNode(nValue);
	sal_Char pCode[32];
		strcpy(pCode, pInCode );

	// query its parents
	sal_Char cLast = pCode[strlen(pCode) - 1];
	pCode[strlen(pCode) - 1] = '\0';
	HuffmanTreeNode * pParent = QueryNode(pCode);
	if (!pParent)
	{
		pParent = InsertNode(0xffffffff, pCode);
	}
	if (cLast == '0')
		pParent->left = pNew;
	else // (cChar == '1')
		pParent->right = pNew;

	return pNew;
}
HuffmanTreeNode * HuffmanTreeNode::QueryNode(const sal_Char * pCode)
{
	sal_uInt32 nLen = strlen(pCode);

	HuffmanTreeNode * pNode = this; // this is the root 
	for(sal_uInt32 i=0; i<nLen && pNode; i++)
	{
		sal_Char cChar= pCode[i];
		if (cChar == '0')
		{
			pNode = pNode->left;
		}
		else // (cChar == '1')
		{
			pNode = pNode->right;
		}
	}
	return pNode;
}

sal_uInt32 HuffmanTreeNode::QueryValue(const sal_Char * pCode)
{
	HuffmanTreeNode * pNode =QueryNode(pCode);
	if (pNode)
		return pNode->value;

	return 0xffffffff;
}

